/* 
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。



输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。



思路：有后效性，考虑动态规划
由于可以从下标为0或1的元素作为初始阶梯，即dp(0)==dp(1)==0
每次可以爬一步或者两步，即判断第i步前的最小花费就是从i-1项和i-2项中取最小花费
dp[i] 表示达到下标 i 的最小花费。
cost[i] 表示第i项的花费
*/
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    const n=cost.length
    // 声明数组dp，每项存储到达此项的最小花费
    let dp=new Array(n+1)
    // 给初始值
    dp[0]=dp[1]=0
    // 遍历台阶数组
    for(let i=2;i<n+1;i++){
        // 到达第i项的最低花费为第i-1项的花费和第i-2项的花费中的较小值
        dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
    }
    // 最后一项就是登顶时的最低花费
    return dp[n]
};

let cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
let res = minCostClimbingStairs(cost)
console.log(res);